package com.linwen.dataStructure.tree;


import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author lin
 * @date 2020年3月1日
 * @version 1.0 
 */
public class BinaryTree {
	//创建二叉树
	public static TreeNode creatBinaryTree(LinkedList<Integer> inputList) {
		TreeNode node = null;
		if(inputList==null||inputList.isEmpty()) {
			return null;
		}
		Integer data = inputList.removeFirst();
		if(data!=null) {
			node = new TreeNode(data);
			node.leftNode = creatBinaryTree(inputList);
			node.rightNode = creatBinaryTree(inputList);
		}
		return node;
	}
	//先序遍历
	public static void preOrderTreavel(TreeNode node) {
		if(node == null) {
			return;
		}
		System.out.print(node.data+"  ");
		preOrderTreavel(node.leftNode);
		preOrderTreavel(node.rightNode);
	}
	//栈的前序遍历
	public  static void stackPreOrderTreavel(TreeNode treeNode){
		//TreeNode treeNode = node;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while (treeNode!=null||!stack.isEmpty()){
			//访问左孩子并入栈
			while (treeNode!=null){
				System.out.print(treeNode.data+"  ");
				stack.push(treeNode);
				treeNode = treeNode.leftNode;
			}
			//如果没有左孩子，出栈 访问右孩子
			if(!stack.isEmpty()){
				treeNode = stack.pop();
				treeNode = treeNode.rightNode;
			}
		}

	}
	//中序遍历
	public static void inderOrderTreavel(TreeNode node) {
		if(node == null) {
			return;
		}
		inderOrderTreavel(node.leftNode);
		System.out.print(node.data+"  ");
		inderOrderTreavel(node.rightNode);
	}
	//后续遍历
	public static void postOrderTreavel(TreeNode node) {
		if(node == null) {
			return;
		}
		postOrderTreavel(node.leftNode);
		postOrderTreavel(node.rightNode);
		System.out.print(node.data+"  ");
	}
	//层次遍历
	public static void levelOrderTreavel(TreeNode node){
		if(node==null){
			return;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(node);
		while (!queue.isEmpty()){
			if(node.leftNode!=null){
				queue.offer(node.leftNode);
			}
			if(node.rightNode!=null){
				queue.offer(node.rightNode);
			}
			System.out.print(queue.poll().data+"  ");
			node = queue.peek();
		}
	}
}
